/**
 * 
 */
package linkedlist.passed;

/**
 * @author xyyi
 *
 */
public class PartitionList {

	/**
	Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

	You should preserve the original relative order of the nodes in each of the two partitions.

	For example,
	Given 1->4->3->2->5->2 and x = 3,
	return 1->2->2->4->3->5.
	 */
	public ListNode partition(ListNode head, int x) {

		ListNode dummyHead = new ListNode(-11);
		ListNode dummyNewHead = new ListNode(-1);
		dummyHead.next = head;
		ListNode curr = dummyHead;
		ListNode newCurr = dummyNewHead;
		while (curr.next != null) {
			if (curr.next.val < x) {
				newCurr.next = curr.next;
				newCurr = newCurr.next;
				curr.next = curr.next.next;

			} else {
				curr = curr.next;
			}

		}
		newCurr.next = dummyHead.next;
		return dummyNewHead.next;

	}

	/**
	 * Definition for singly-linked list.
	 */
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	/**
	 * 
	 */
	public PartitionList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
